//树可以看成是一个连通且 无环 的 无向 图。
//
// 给定往一棵 n 个节点 (节点值 1～n) 的树中添加一条边后的图。添加的边的两个顶点包含在 1 到 n 中间，且这条附加的边不属于树中已存在的边。图的信
//息记录于长度为 n 的二维数组 edges ，edges[i] = [ai, bi] 表示图中在 ai 和 bi 之间存在一条边。
//
// 请找出一条可以删去的边，删除后可使得剩余部分是一个有着 n 个节点的树。如果有多个答案，则返回数组 edges 中最后出现的边。
//
//
//
// 示例 1：
//
//
//
//
//输入: edges = [[1,2],[1,3],[2,3]]
//输出: [2,3]
//
//
// 示例 2：
//
//
//
//
//输入: edges = [[1,2],[2,3],[3,4],[1,4],[1,5]]
//输出: [1,4]
//
//
//
//
// 提示:
//
//
// n == edges.length
// 3 <= n <= 1000
// edges[i].length == 2
// 1 <= ai < bi <= edges.length
// ai != bi
// edges 中无重复元素
// 给定的图是连通的
//
//
//
//
//
// 注意：本题与主站 684 题相同： https://leetcode-cn.com/problems/redundant-connection/
//
// Related Topics 深度优先搜索 广度优先搜索 并查集 图 👍 49 👎 0


//leetcode submit region begin(Prohibit modification and deletion)
function findRedundantConnection(edges: number[][]): number[] {
    /*
        ? 如果两个顶点属于不同的连通分量，则说明在遍历到当前的边之前，这两个顶点之间不连通，因此当前的边不会导致环出现，合并这两个顶点的连通分量。
        ? 如果两个顶点属于相同的连通分量，则说明在遍历到当前的边之前，这两个顶点之间已经连通，因此当前的边导致环出现，为附加的边，将当前的边作为答案返回。
         */
    const n = edges.length;
    //? 并查集初始
    const parent = new Array(n + 1).fill(0).map((value, index) => index);
    for (let i = 0; i < n; i++) {
        const edge = edges[i];
        const node1 = edge[0], node2 = edge[1];
        //? 两个顶点的父同不同
        if (find(parent, node1) != find(parent, node2)) {
            //? 不同 需要合并了
            union(parent, node1, node2);
        } else {
            //? 两个父相同 说明已经联通 故此边会导致环的出现 返回结果
            return edge;
        }
    }
    return [0];
};
//? 合并
const union = (parent, index1, index2) => {
    parent[find(parent, index1)] = find(parent, index2);
}
//? 找老汉
const find = (parent, index) => {
    if (parent[index] !== index) {
        parent[index] = find(parent, parent[index]);
    }
    return parent[index];
};
//leetcode submit region end(Prohibit modification and deletion)
